#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/24 10:33
# ===========================================
#       题目名称： 34. 在排序数组中查找元素的第一个和最后一个位置
#       题目地址： https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
#       题目描述： https://note.youdao.com/s/RRXNSXjR
# ===========================================


class Solution:
    """
        实现思路：
            二分查找
            实现时间复杂度为 O(log n) 的算法解决此问题
    """

    def searchRange(self, nums, target):
        # 返回值
        res_list = [-1, -1]
        # 不允许都为空
        if not nums:
            return res_list
        # 定义左右指针
        left, right, left_ok, right_ok = 0, len(nums) - 1, False, False
        while left <= right:
            if not left_ok:
                if nums[left] == target:
                    res_list[0] = left
                    left_ok = True
                else:
                    left += 1
            if not right_ok:
                if nums[right] == target:
                    res_list[1] = right
                    right_ok = True
                else:
                    right -= 1
            if left_ok and right_ok:
                break
        return res_list


if __name__ == '__main__':
    s = Solution()
    # [3,4]
    print(s.searchRange(nums=[5, 7, 7, 8, 8, 10], target=8))
    # [-1,-1]
    print(s.searchRange(nums=[5, 7, 7, 8, 8, 10], target=6))
    # [-1,-1]
    print(s.searchRange(nums=[], target=0))
    # [0,0]
    print(s.searchRange(nums=[1, ], target=1))
    # [0,1]
    print(s.searchRange(nums=[2, 2], target=2))
    # [0,0]
    print(s.searchRange(nums=[1, 3], target=1))
    # [1,1]
    print(s.searchRange(nums=[1, 4], target=4))
    # [1,1]
    print(s.searchRange(nums=[1, 2, 3], target=2))
    # [1,2]
    print(s.searchRange(nums=[1, 2, 2], target=2))
